//! 双向链表核心类型定义模块
//!
//! 包含链表值类型、比较函数类型等基础类型定义

use std::cmp::Ordering;
use std::ffi::c_void;

/// 链表值类型别名（保持与C代码兼容的过渡方案）
/// 后续应替换为泛型实现
pub type ListValue = *const c_void;

/// 链表比较函数类型（过渡方案）
/// 参数为两个待比较的链表值，返回标准排序顺序
/// 后续应升级为使用泛型和 `Fn` trait bound
pub type ListCompareFunc = unsafe fn(ListValue, ListValue) -> Ordering;

/// 链表相等判断函数类型（过渡方案）
/// 参数为两个待比较的链表值，返回布尔判断结果
/// 后续应升级为使用泛型和 `Fn` trait bound
pub type ListEqualFunc = unsafe fn(ListValue, ListValue) -> bool;

/// 空指针常量（保持与C代码兼容）
/// 后续应使用Option<Pointer>替代裸指针
pub const LIST_NULL: ListValue = std::ptr::null();


/// 双向链表节点结构（过渡方案）
///
/// 保持与C代码兼容的原始字段布局，包含：
/// - data: 使用裸指针存储的链表值
/// - prev/next: 原始指针实现的邻节点链接
/// 后续应替换为使用泛型T和智能指针的安全实现
#[derive(Debug)]
pub struct ListEntry {
    pub data: ListValue,
    pub prev: *mut ListEntry,
    pub next: *mut ListEntry,
}

/// 对双向链表进行快速排序的内部实现
///
/// # 安全性
///
/// 调用者需要确保：
/// - `list` 是有效的链表头指针的指针
/// - `compare_func` 是有效的比较函数
/// - 链表节点间的指针关系正确
unsafe fn list_sort_internal(list: *mut *mut ListEntry, compare_func: ListCompareFunc) -> *mut ListEntry {
    if list.is_null() || compare_func as usize == 0 {
        return std::ptr::null_mut();
    }

    let mut current = *list;
    if current.is_null() || (*current).next.is_null() {
        return current;
    }

    let pivot = current;
    let mut less = std::ptr::null_mut();
    let mut greater = std::ptr::null_mut();
    let mut next = (*current).next;

    while !next.is_null() {
        let temp = (*next).next;
        if compare_func((*next).data, (*pivot).data) == Ordering::Less {
            (*next).prev = std::ptr::null_mut();
            (*next).next = less;
            if !less.is_null() {
                (*less).prev = next;
            }
            less = next;
        } else {
            (*next).prev = std::ptr::null_mut();
            (*next).next = greater;
            if !greater.is_null() {
                (*greater).prev = next;
            }
            greater = next;
        }
        next = temp;
    }

    let less_end = list_sort_internal(&mut less, compare_func);
    let greater_end = list_sort_internal(&mut greater, compare_func);

    unsafe {
        *list = less;
        if less.is_null() {
            (*pivot).prev = std::ptr::null_mut();
            *list = pivot;
        } else {
            (*less_end).next = pivot;
            (*pivot).prev = less_end;
        }

        (*pivot).next = greater;
        if !greater.is_null() {
            (*greater).prev = pivot;
        }
    }

    if greater.is_null() { pivot } else { greater_end }
}

/// 对双向链表进行快速排序的公共接口
///
/// # 参数
/// - `list`: 可变引用指向链表头指针
/// - `compare_func`: 用于元素比较的函数指针
///
/// # 安全性
/// 调用者需要确保链表指针有效且比较函数行为正确
pub unsafe fn list_sort(list: &mut *mut ListEntry, compare_func: ListCompareFunc) {
    list_sort_internal(list as *mut _ as *mut *mut ListEntry, compare_func);
}

/// 双向链表迭代器结构（过渡方案）
///
/// 保持与C代码兼容的原始字段布局，包含：
/// - `prev_next`: 用于修改前序节点next指针的双重指针
/// - `current`: 当前迭代位置的节点指针
/// 后续应升级为基于Rust迭代器特性的安全实现
#[derive(Debug)]
pub struct ListIterator {
    pub prev_next: *mut *mut ListEntry,
    pub current: *mut ListEntry,
}

/// Prepends a new entry to the beginning of the list.
///
/// # Arguments
/// * `list` - Mutable reference to the head pointer of the list
/// * `data` - Data to store in the new entry
///
/// # Returns
/// Pointer to the newly created list entry
///
/// # Safety
/// This function manipulates raw pointers and requires:
/// 1. Valid list head pointer (may be null)
/// 2. Proper memory management for the stored data
pub unsafe fn list_prepend(list: &mut *mut ListEntry, data: ListValue) -> *mut ListEntry {
    let new_entry = Box::into_raw(Box::new(ListEntry {
        data,
        prev: std::ptr::null_mut(),
        next: *list,
    }));

    if !(*list).is_null() {
        (**list).prev = new_entry;
    }

    *list = new_entry;
    new_entry
}

/// 获取链表节点的前驱节点指针
///
/// # 安全
/// 调用者必须保证传入的指针有效或为空
///
/// # 参数
/// - `entry`: 指向链表节点的原始指针
///
/// # 返回值
/// 前驱节点指针（可能为空）
pub unsafe fn list_prev(entry: *mut ListEntry) -> *mut ListEntry {
    if entry.is_null() {
        return std::ptr::null_mut();
    }
    (*entry).prev
}

/// 获取链表节点的后继节点指针
///
/// # 安全
/// 调用者必须保证传入的指针有效或为空
///
/// # 参数
/// - `entry`: 指向链表节点的原始指针
///
/// # 返回值
/// 后继节点指针（可能为空）
pub unsafe fn list_next(entry: *mut ListEntry) -> *mut ListEntry {
    if entry.is_null() {
        return std::ptr::null_mut();
    }
    (*entry).next
}

/// 获取链表中第n个节点的指针
///
/// # 参数
/// - `list`: 链表头节点指针
/// - `n`: 从0开始的索引位置
///
/// # 返回
/// 指向第n个节点的指针，若索引越界返回空指针
///
/// # 安全性
/// 调用者需要确保：
/// - 链表指针有效（可为空）
/// - n不超过链表实际长度
#[inline]
pub unsafe fn list_nth_entry(list: *mut ListEntry, n: u32) -> *mut ListEntry {
    let mut entry = list;
    for _ in 0..n {
        if entry.is_null() {
            return std::ptr::null_mut();
        }
        entry = (*entry).next;
    }
    entry
}

/// 获取链表中第n个节点的数据
///
/// # 参数
/// - `list`: 链表头节点指针
/// - `n`: 从0开始的索引位置
///
/// # 返回
/// 节点数据指针，若索引越界返回LIST_NULL
///
/// # 安全性
/// 需要满足list_nth_entry的所有安全条件
#[inline]
pub unsafe fn list_nth_data(list: *mut ListEntry, n: u32) -> ListValue {
    match list_nth_entry(list, n) {
        ptr if ptr.is_null() => LIST_NULL,
        entry => (*entry).data,
    }
}

/// 从链表中移除符合条件的数据项
///
/// # 参数
/// - `list`: 可变引用指向链表头指针
/// - `callback`: 数据匹配判断函数
/// - `data`: 待匹配数据指针
///
/// # 返回值
/// 被移除的节点数量
///
/// # 安全性
/// 调用者需保证链表指针有效性及回调函数线程安全
pub unsafe fn list_remove_data(
    list: &mut *mut ListEntry,
    callback: ListEqualFunc,
    data: ListValue,
) -> u32 {
    let mut count = 0;
    let mut current = *list;
    let mut prev_ptr: *mut *mut ListEntry = list;

    while !current.is_null() {
        let next = unsafe { (*current).next };
        
        if unsafe { callback((*current).data, data) } {
            // 调整前驱节点指针
            unsafe { *prev_ptr = next };
            
            // 调整后继节点指针
            if !next.is_null() {
                unsafe { (*next).prev = (*current).prev };
            }

            // 释放节点内存
            drop(unsafe { Box::from_raw(current) });
            count += 1;
        } else {
            // 更新前驱指针位置
            prev_ptr = unsafe { &mut (*current).next };
        }

        current = next;
    }

    count
}

/// 获取链表节点存储的数据值
///
/// # 参数
/// - `entry`: 指向链表节点的原始指针
///
/// # 返回值
/// 节点数据指针，若节点为空则返回LIST_NULL
///
/// # 安全性
/// 调用者必须保证传入的指针有效或为空
pub unsafe fn list_data(entry: *mut ListEntry) -> ListValue {
    if entry.is_null() {
        return LIST_NULL;
    }
    unsafe { (*entry).data }
}

/// 设置链表节点存储的数据值
///
/// # 参数
/// - `entry`: 指向链表节点的原始指针
/// - `value`: 要设置的新数据值
///
/// # 安全性
/// 调用者必须保证传入的指针有效或为空
pub unsafe fn list_set_data(entry: *mut ListEntry, value: ListValue) {
    if !entry.is_null() {
        unsafe { (*entry).data = value; }
    }
}

/// 从链表中移除指定节点
///
/// # 参数
/// - `list`: 可变引用指向链表头指针
/// - `entry`: 要移除的节点指针
///
/// # 返回值
/// 成功移除返回1，失败返回0
///
/// # 安全性
/// 调用者必须保证：
/// - `list` 和 `entry` 是有效指针
/// - `entry` 确实属于该链表
#[inline]
pub unsafe fn list_remove_entry(list: &mut *mut ListEntry, entry: *mut ListEntry) -> u32 {
    if list.is_null() || (*list).is_null() || entry.is_null() {
        return 0;
    }

    // 处理头节点的情况
    if (*entry).prev.is_null() {
        *list = (*entry).next;
        if !(*entry).next.is_null() {
            (*(*entry).next).prev = std::ptr::null_mut();
        }
    } else {
        (*(*entry).prev).next = (*entry).next;
        if !(*entry).next.is_null() {
            (*(*entry).next).prev = (*entry).prev;
        }
    }

    // 释放节点内存
    drop(Box::from_raw(entry));
    1
}

/// 释放整个链表占用的内存
///
/// # 参数
/// - `list`: 链表头节点指针
///
/// # 安全性
/// 调用者必须保证：
/// - 链表指针有效（可为空指针）
/// - 链表节点间的指针关系正确
/// - 函数执行后不再访问已被释放的节点
pub unsafe fn list_free(list: *mut ListEntry) {
    let mut current = list;
    while !current.is_null() {
        let next = (*current).next;
        // 将裸指针转换回Box以触发内存释放
        drop(Box::from_raw(current));
        current = next;
    }
}

/// 在链表中查找匹配指定数据的节点
///
/// # 参数
/// - `list`: 链表头节点指针
/// - `callback`: 数据匹配判断函数
/// - `data`: 待匹配数据指针
///
/// # 返回值
/// 指向匹配节点的指针，未找到返回空指针
///
/// # 安全性
/// 调用者必须保证：
/// - 链表指针有效性（可为空）
/// - 回调函数线程安全且符合内存安全
pub unsafe fn list_find_data(
    list: *mut ListEntry,
    callback: ListEqualFunc,
    data: ListValue,
) -> *mut ListEntry {
    let mut rover = list;

    while !rover.is_null() {
        if callback((*rover).data, data) {
            return rover;
        }
        rover = (*rover).next;
    }

    std::ptr::null_mut()
}

/// 初始化链表迭代器，准备从头开始遍历链表
///
/// # 参数
/// - `list`: 可变引用指向链表头指针
/// - `iter`: 可变指针指向要初始化的迭代器实例
///
/// # 安全性
/// 调用者必须确保：
/// - `list` 是有效的链表头指针的引用
/// - `iter` 是有效且可写的指针
/// - 迭代器生命周期内链表结构保持有效
#[inline]
pub unsafe fn list_iterate(list: &mut *mut ListEntry, iter: *mut ListIterator) {
    unsafe {
        (*iter).prev_next = list as *mut _;
        (*iter).current = std::ptr::null_mut();
    }
}

/// 计算链表长度
///
/// # 参数
/// - `list`: 链表头节点指针（可为空）
///
/// # 返回值
/// 链表包含的节点数量
///
/// # 安全性
/// 调用者需确保指针有效性（允许空指针）
pub unsafe fn list_length(list: *mut ListEntry) -> u32 {
    let mut length = 0;
    let mut entry = list;

    while !entry.is_null() {
        length += 1;
        entry = (*entry).next;
    }

    length
}

/// 将链表转换为堆分配数组
///
/// # 参数
/// - `list`: 链表头节点指针（可为空）
///
/// # 返回值
/// 包含链表数据的数组指针，需用Box::from_raw释放内存
/// 空链表或分配失败时返回空指针
///
/// # 安全性
/// 调用者需保证:
/// 1. 链表在转换期间保持稳定
/// 2. 通过返回指针访问数据时链表未被修改
pub unsafe fn list_to_array(list: *mut ListEntry) -> *mut ListValue {
    let length = list_length(list);
    if length == 0 {
        return std::ptr::null_mut();
    }

    let mut array = Vec::with_capacity(length as usize);
    let mut rover = list;

    while !rover.is_null() {
        array.push((*rover).data);
        rover = (*rover).next;
    }

    Box::into_raw(array.into_boxed_slice()) as *mut ListValue
}

/// 在链表尾部追加新节点
///
/// # 参数
/// - `list`: 可变引用指向链表头指针
/// - `data`: 要存储的数据指针
///
/// # 返回
/// 新创建的节点指针
///
/// # 安全性
/// 调用者必须确保：
/// - `list` 是有效的链表头指针的可变引用
/// - 数据指针的生命周期管理正确
pub unsafe fn list_append(list: &mut *mut ListEntry, data: ListValue) -> *mut ListEntry {
    let new_entry = Box::into_raw(Box::new(ListEntry {
        data,
        prev: std::ptr::null_mut(),
        next: std::ptr::null_mut(),
    }));

    if (*list).is_null() {
        *list = new_entry;
    } else {
        let mut rover = *list;
        while !(*rover).next.is_null() {
            rover = (*rover).next;
        }
        (*rover).next = new_entry;
        (*new_entry).prev = rover;
    }

    new_entry
}

/// 通过迭代器安全移除当前链表节点
///
/// # 参数
/// - `iter`: 可变指针指向链表迭代器实例
///
/// # 安全性
/// 调用者必须确保：
/// - `iter` 是有效且可写的指针
/// - 迭代器关联的链表在操作期间保持有效
/// - 被移除的节点在函数返回后不再被访问
#[inline]
pub unsafe fn list_iter_remove(iter: *mut ListIterator) {
    if iter.is_null() {
        return;
    }

    let current = unsafe { (*iter).current };
    let prev_next = unsafe { (*iter).prev_next };

    if current.is_null() || current != unsafe { *prev_next } {
        return;
    }

    unsafe {
        *prev_next = (*current).next;
        if let Some(next) = (*current).next.as_mut() {
            next.prev = (*current).prev;
        }
        Box::from_raw(current);
        (*iter).current = std::ptr::null_mut();
    }
}

/// 判断迭代器是否还有更多可遍历的节点
///
/// # 参数
/// - `iter`: 可变引用指向链表迭代器实例
///
/// # 返回值
/// 如果存在下一个可访问节点返回true，否则返回false
///
/// # 安全性
/// 调用者必须确保：
/// - 迭代器实例指针有效
/// - 在调用期间链表结构保持稳定
pub unsafe fn list_iter_has_more(iter: &mut ListIterator) -> bool {
    unsafe {
        if iter.current.is_null() || iter.current != *iter.prev_next {
            // 处理未读取首节点/当前节点被移除/到达链表末尾的情况
            !(*iter.prev_next).is_null()
        } else {
            // 当前节点未被移除时检查后继节点是否存在
            !(*iter.current).next.is_null()
        }
    }
}

/// 获取链表迭代器的下一个元素数据
///
/// # 参数
/// - `iter`: 指向链表迭代器的可变指针
///
/// # 返回值
/// 下一个节点的数据指针，若到达链表末尾返回LIST_NULL
///
/// # 安全性
/// 调用者必须确保：
/// - `iter` 是有效且可写的指针
/// - 迭代期间链表结构未被修改
/// - 迭代器生命周期内链表保持内存有效
pub unsafe fn list_iter_next(iter: *mut ListIterator) -> ListValue {
    unsafe {
        if (*iter).current.is_null() || (*iter).current != *(*iter).prev_next {
            (*iter).current = *(*iter).prev_next;
        } else {
            (*iter).prev_next = &mut (*(*iter).current).next;
            (*iter).current = (*(*iter).current).next;
        }

        if (*iter).current.is_null() {
            LIST_NULL
        } else {
            (*(*iter).current).data
        }
    }
}